﻿//
// Find boundaries for things that can't use tile-based positioning.
//
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BoatNGoat.Logic.Map
{

    struct BoundaryPixel
    {
        public int x;
        public int y;

        // Map 2D points in the neighbourhood to scalar angles
        // about the centre. Angles are defined by the values in this
        // array. A clockwise move is defined as angle += 1.
        private static int[] ANGLE_TABLE = new int[]
        {
            1, 2, 3,
            0, 8, 4,
            7, 6, 5
        };

        public BoundaryPixel(int ix, int iy) { x = ix; y = iy; }

        public bool EqualTo(BoundaryPixel other)
        {
            return other.x == x && other.y == y;
        }

        // Find the next pixel clockwise from b in this pixel's
        // moore neighbourhood. b must also be in this pixel's
        // moore neighbourhood.
        public BoundaryPixel NextClockwisePixel(BoundaryPixel b)
        {
            int a = GetAngle(b);
            a += 1;
            return GetPixel(a);
        }

        private int GetAngle(BoundaryPixel b)
        {
            // Map deltas to [0, 3)
            int deltaX = x - b.x + 1;
            int deltaY = y - b.y + 1;

            if ((0 <= deltaX && deltaX < 3) &&
                (0 <= deltaY && deltaY < 3))
            {
                return ANGLE_TABLE[deltaX + deltaY * 3];
            }
            else
            {
                throw new IndexOutOfRangeException("boundary pixel not part of this neighbourhood");
            }
        }

        private BoundaryPixel GetPixel(int a)
        {
            for (int i = 0; i < ANGLE_TABLE.Length; ++i)
            {
                if (a == ANGLE_TABLE[i])
                    return new BoundaryPixel(i % 3, i / 3);
            }
            throw new IndexOutOfRangeException("boundary pixel not part of this neighbourhood");
        }

        public MapPosition TopLeftPosition()
        {
            return new MapPosition((float)x, (float)y);
        }

        /// <summary>
        /// If there is a corner position between this and next when
        /// boundary generating then return that position.
        /// Next must be joined within this pixel's neighbourhood.
        /// </summary>
        /// <param name="next">the next pixel in the path</param>
        /// <returns>corner position or null - check ang get using .HasValue and .Value</returns>
        public MapPosition? CornerPosition(BoundaryPixel next)
        {
            int delta_x = next.x - x;
            int delta_y = next.y - y;

            // Are the pixels unjoined?
            if (System.Math.Abs(delta_x) != 1 ||
                System.Math.Abs(delta_y) != 1)
            {
                return null;
            }

            int total_distance = System.Math.Abs(delta_x) + System.Math.Abs(delta_y);
            bool corner = total_distance > 1;
            if (corner)
            {
                bool move_along_y_first = delta_x < 0;
                if (move_along_y_first)
                    return new MapPosition((float)x, (float)(y + delta_y));
                else
                    return new MapPosition((float)(x + delta_x), (float)y);
            }
            else
            {
                return null;
            }
        }
    }


    class Boundary
    {
        public List<MapPosition> Points;
        public readonly bool Closed = true;

        public Boundary(List<BoundaryPixel> pixels)
        {
            // TODO implement
            Points = new List<MapPosition>();
            Fill(pixels);
        }

        static private bool CornerExists(MapPosition? p)
        {
            return p.HasValue;
        }

        private void Fill(List<BoundaryPixel> pixels)
        {
            if (pixels.Count == 0)
                return;

            BoundaryPixel previous = pixels[0];
            for (int i = 1; i < pixels.Count; ++i)
            {
                Points.Add(previous.TopLeftPosition());

                BoundaryPixel current = pixels[i];
                MapPosition? boundary_point = previous.CornerPosition(current);
                if (CornerExists(boundary_point))
                    Points.Add(boundary_point.Value);
            }
            BoundaryPixel last = pixels.Last();
            Points.Add(last.TopLeftPosition());
        }
    }

    /// <summary>
    /// Finds a set of vector polygons that enclose the
    /// desired map features. The polygons are closed and,
    /// if necessary, clipped to the map bounds
    /// </summary>
    class BoundaryFinder
    {
        private readonly IMap _map;
        private readonly Tile _type;
        private List<Boundary> _boundaries;
        private BoundaryPixel _previousSearchPixel;
        private MapBox2 _restrict;

        /// <summary>
        /// Find boundaries of this tile type on the map.
        /// </summary>
        /// <param name="map"></param>
        /// <param name="type"></param>
        public BoundaryFinder(IMap map, Tile type, MapBox2 restrict)
        {
            _map = map;
            _type = type;
            _boundaries = new List<Boundary>();
            _previousSearchPixel = new BoundaryPixel(0, 0);
            _restrict = restrict;
        }

        /// <summary>
        /// Returns true if this feature should be inside
        /// the boundary.
        /// </summary>
        /// <param name="testPoint"></param>
        /// <returns></returns>
        private bool IsBlack(Tile testPoint)
        {
            return testPoint == _type;
        }

        /// <summary>
        /// Include this pixel inside the boundary?
        /// </summary>
        /// <param name="testPoint"></param>
        /// <returns></returns>
        private bool IsBlack(BoundaryPixel pixel)
        {
            return IsBlack(_map.Tiles[pixel.x, pixel.y]);
        }

        /// <summary>
        /// Include this pixel inside the boundary?
        /// </summary>
        /// <param name="testPoint"></param>
        /// <returns></returns>
        private bool IsBlack(int x, int y)
        {
            return IsBlack(_map.Tiles[x, y]);
        }

        /// <summary>
        /// Returns the next black pixel or null if the search exhausted
        /// the map without finding one.
        /// </summary>
        /// <param name="startX"></param>
        /// <param name="startY"></param>
        /// <returns></returns>
        private BoundaryPixel? ScanForNextBlackPixel(BoundaryPixel startPixel)
        {
            // Bottom to top, then left to right.
            for (int x = startPixel.x; x < _map.Width; x += 1)
            {
                for (int y = startPixel.y; y < _map.Height; y += 1)
                {
                    if (IsBlack(x, y))
                    {
                        return new BoundaryPixel(x, y);
                    }
                }
            }

            return null;
        }

        /// <summary>
        /// Implement moore's neighbourhood algorithm.
        /// </summary>
        private void MooreNeighbourhoodScan()
        {
            var outputCurve = new List<BoundaryPixel>();
            BoundaryPixel initial = new BoundaryPixel(0, 0);
            BoundaryPixel? startOfBoundary = ScanForNextBlackPixel(initial);
            if (!startOfBoundary.HasValue) // no more boundaries found
            {
                return;
            }

            // Start searching until we get to the start of the curve.
            outputCurve.Add(startOfBoundary.Value);
            BoundaryPixel endOfBoundary = startOfBoundary.Value;
            BoundaryPixel backtrack = _previousSearchPixel;
            BoundaryPixel candidate = endOfBoundary.NextClockwisePixel(backtrack);
            while (!candidate.EqualTo(startOfBoundary.Value))
            {
                if (IsBlack(candidate))
                {
                    outputCurve.Add(candidate);
                    backtrack = endOfBoundary;
                    endOfBoundary = candidate;
                    candidate = endOfBoundary.NextClockwisePixel(backtrack);
                }
                else
                {
                    backtrack = candidate;
                    candidate = endOfBoundary.NextClockwisePixel(backtrack);
                }
            }

            Boundary outlined = new Boundary(outputCurve);
            _boundaries.Add(outlined);
        }

    }
}
